'''
给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：
输入：s = "banana"
输出："ana"

示例 2：
输入：s = "abcd"
输出：""


提示：
2 <= s.length <= 3 * 104
s 由小写英文字母组成
'''

'''
要解决 “最长重复子串” 问题，我们可以使用 ** 二分查找 + 滚动哈希（Rabin-Karp 算法）** 的方法。思路是：通过二分查找确定可能的子串长度，再用滚动哈希快速判断该长度下是否存在重复子串。
代码解释
滚动哈希（Rabin-Karp）：
将字符串的子串转换为数值哈希，通过滚动计算相邻子串的哈希值，避免重复计算，时间复杂度为O(n)
这里使用基数 26（因为字符串由小写字母组成）和大模数 10^18 + 3 减少哈希冲突。
二分查找：
二分查找可能的子串长度（范围是 0 到字符串长度 n）。
对于每个中间长度 mid，调用 check 函数判断是否存在该长度的重复子串。
如果存在，尝试更长的长度（调整左边界）；否则，尝试更短的长度（调整右边界）。
哈希冲突处理：
当发现哈希值重复时，需要实际比较子串内容，避免哈希冲突导致的错误判断。
这种方法的时间复杂度为O(nlogn)，在处理较长字符串时效率较高。

'''

def longestDupSubstring(s):
    n = len(s)
    # 定义滚动哈希的基数和模数
    base = 26
    mod = 10**18 + 3

    def check(length):
        if length == 0:
            return ""
        # 计算初始窗口的哈希值和幂次
        hash_val = 0
        power = 1
        for i in range(length):
            hash_val = (hash_val * base + (ord(s[i]) - ord('a'))) % mod
            power = (power * base) % mod
        # 存储哈希值对应的起始索引
        seen = {hash_val: 0}
        for i in range(1, n - length + 1):
            # 滚动计算当前窗口的哈希值
            hash_val = (hash_val * base - (ord(s[i - 1]) - ord('a')) * power + (ord(s[i + length - 1]) - ord('a'))) % mod
            if hash_val in seen:
                # 检查是否真的重复（避免哈希冲突）
                start = seen[hash_val]
                if s[start:start + length] == s[i:i + length]:
                    return s[i:i + length]
            seen[hash_val] = i
        return ""

    # 二分查找最长长度
    left, right = 0, n
    result = ""
    while left <= right:
        mid = (left + right) // 2
        current = check(mid)
        if len(current) > len(result):
            result = current
            left = mid + 1
        else:
            right = mid - 1
    return result


print(longestDupSubstring("banana"))
print(longestDupSubstring("abcd"))
